1. Field of the Invention
The present invention relates to communications devices, specifically linecards for interfacing communications devices to networks.
2. Description of the Related Art
In a communications network, routing devices receive messages at one of a set of input interfaces and forward them on to one of a set of output interfaces. Users typically require that such routing devices operate as quickly as possible in order to keep up with the high rate of incoming messages. In a packet routing network, wherein information is transmitted in discrete chunks or xe2x80x9cpacketsxe2x80x9d of data, each packet includes a header. The header contains information used for routing the packet to an output interface and subsequent forwarding to a destination device. The packet may also be forwarded to another router for further processing and/or forwarding. Header information used for routing may include the destination address and source address for the packet. Additionally, header information such as the destination device port, source device port, protocol, and packet priority may be used. Header information used by routing devices for administrative tasks may include information about access control, accounting, quality of service (QoS), or class of service (CoS).
FIG. 1 is a generic routing system 100 that will be used to describe both the prior art and the invention. A well-known routing device or system 100 consists of a set of linecards 110 and a switching fabric 120. Each linecard 110 includes an input interface 111, an output interface 112, a fabric interface 170, and a control element 130. Linecards 110 connect to communications network 1, which may be any form of local, enterprise, metropolitan, or wide area network known in the art, through both input interface 111 and output interface 112.
Control element 130 is configured to receive inbound packets 113 (i.e., packets entering the system from network 1) from input interface 111, process the packet, and transmit it through fabric interface 170 to switching fabric 120 for further processing by the same or another control element 130. Outbound packets 114 are received from switching fabric 120 through fabric interface 170, processed in control element 130, and transmitted to network 1 on output interface 112.
Control element 130 consists of an inbound packet receiver 140, lookup circuit 145, inbound memory controller 150, first memory 160, fabric interface 170, outbound memory controller 150, second memory 160, and outbound transmitter 180. Control circuits 190 are also provided to perform statistics collection and accounting functions as well as to process certain exception packets.
In a manner well-known in the art, packets are received from the physical medium of the network at input interface 111. The inbound packet receiver 140 operates in conjunction with lookup circuit 145 to determine routing treatments for inbound packets 113. Lookup circuit 145 includes routing treatment information disposed in a memory data structure. Access and use of this information in response to data in the header portion of inbound packet 113 is accomplished with means well-known in the router art. These routing treatments can include one or more of the following:
a) selection of one or more output interfaces to which to forward inbound packets 113 responsive to the destination device, to the source and destination device, or to any other packet header information;
b) determination of class of service (CoS) treatment for inbound packets 113;
c) determination of one or more accounting records or treatments for inbound packets 113; and
d) determination of other administrative treatment for inbound packets 113.
Examples of such systems may be found in U.S. Pat. Nos. 5,088,032, METHOD AND APPARATUS FOR ROUTING COMMUNICATIONS AMONG COMPUTER NETWORKS to Leonard Bosack; U.S. Pat. No. 5,509,006, APPARATUS AND METHOD FOR SWITCHING PACKETS USING TREE MEMORY to Bruce Wilford et al.; U.S. Pat. No. 5,852,655, COMMUNICATION SERVER APPARATUS HAVING DISTRIBUTED SWITCHING AND METHOD to John McHale et al.; and U.S. Pat. No. 5,872,783, ARRANGEMENT FOR RENDERING FORWARDING DECISIONS FOR PACKETS TRANSFERRED AMONG NETWORK SWITCHES to Hon Wah Chin, incorporated in their entireties herein by reference.
One shortcoming known in the prior art arises from the ever-increasing need for speed in network communications. Attempts to scale prior art routers and switches to gigabit speed have shown that architectures that require a deep packet buffering prior to determining routing treatment suffer from high packet latency. Distributed routing schemes, such as that described above wherein routing is performed immediately on packet receipt in each linecard, have had only limited success in providing the necessary increase in throughput speed.
A further drawback of prior art systems is their relative inability to rapidly provide a range of services based on packet priority, as represented by various fields in the packet header. Such systems are often described as providing type of service (TOS), quality of service (QoS), or class of service (CoS) routing. Prior art systems typically experience additional packet latency and throughput reduction when performing routing based on packet priority.
What is needed is a router/switch system, preferably distributed on a linecard, that provides low latency packet routing based at least in part on packet priority. In particular, low latency priority routing determined by individual packet class of service is desired. Such a linecard should operate as close to line rate as possible, i.e., at or near the maximum speed of transmission over the physical medium and without any appreciable buffering delay.
The present invention is a linecard architecture for high speed routing of data in a communications device. This architecture provides low latency routing based on packet priority because packet routing and processing occurs at line rate (i.e., at wire speed) for most operations. Comprised of an inbound receiver (including lookup and packet modification functions), queue manager, and outbound transmitter portions with associated network physical interfaces and a common device switching fabric, the architecture provides a distributed routing function with minimal packet delay.
Packets arrive from the network via a physical medium interface, in one embodiment an OC192 fiber optic connection. Demodulation, deframing, and conditioning are performed by means well-known in the art to supply an OSI layer 3 packet data stream to the inbound receiver. The inbound receiver uses a small, single packet FIFO to accumulate packet bytes very rapidly, at line rate. Once the header portion of the packet, in one embodiment defined as the first 60 bytes, is received, it is used to rapidly perform a routing lookup. The lookup data returned is then used to modify the packet header, and rate limiting and buffer management rules are applied to the packet. All of the above steps occur essentially at line rate, without the buffering-induced delay seen in the prior art.
The queue manager uses the class of service information in the packet header to enqueue the packet according to its required priority, again at essentially line rate. Enqueued packets are buffered in a large memory space holding multiple packets prior to transmission across the device""s switch fabric (interconnect) to the outbound linecard.
On arrival at the outbound linecard, the packet is (in one embodiment of the present invention) rate limited and enqueued in the outbound transmitter portion of the linecard architecture. A large, multi-packet memory structure, as employed in the inbound queue manager, provides buffering prior to transmission onto the network via an appropriate physical layer interface module.